package algorithm.slidingwindow;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 239. Sliding Window Maximum
 * leetcode: https://leetcode.com/problems/sliding-window-maximum/
 * Difficulty: Hard
 *
 * 典型滑动窗口算法。
 * 描述：给一个数组num 和一个数字 k，k表示滑动窗口的大小。
 * 你只能看到窗口内的数字，每次窗口滑动一格。
 * 返回滑动窗口中，窗口里数字的最大值，组成的数组。
 *
 * 举栗：
 * Input: nums=[1,3,-1,-3,5,3,6,7], k=3
 * OutPut: [3,3,5,5,6,7]
 *
 * 可以假定k总是有效的， 1<= k <=array.size
 * 【关键】：在线性的时间复杂度内解决
 *
 * 参考: 石杉的架构笔记 https://mp.weixin.qq.com/s/_8durJjEK-joCLNa58auOQ
 *
 *
 * Created by yzy on 2019-05-05 17:20
 */
public class SlidingWindowMaximun {

    /**
     * 10ms, 76.37%
     * 42.2MB, 65.32%
     *
     * 思路：使用双端队列Deque
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k){
        if(nums==null || nums.length<=0 ){
            return new int[0];
        }
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();  // 保存的是nums数组里的索引
        for(int i=0; i<nums.length; i++){
            // 保证队列尾部索引对应nums的值，不比当前nums[i]的值小 (大于等于)(也就是严格按从大到小值 的 index 顺序)
            while(!deque.isEmpty() && nums[i] >nums[deque.getLast()]){
                deque.removeLast();
            }

            // 向队列尾部添加元素(index)
            deque.addLast(i);

            // 移除超出窗口的头部元素(index)
            if(deque.getFirst() <= i-k){
                deque.removeFirst();
            }

            // 保存结果(当i移动到窗口大小时才开始保存结果)
            if(i>=k-1){
                res[i-k+1] = nums[deque.getFirst()];
            }
        }

        return res;
    }



    // TODO
    public static int[] maxSlidingWindow_test(int[] nums, int k) {
        if(nums==null || nums.length==0) {
            return null;
        }

        // 结果集
        int[] res = new int[nums.length-k + 1];
        // 双端队列
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0; i<nums.length; i++){
            while(!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
                deque.removeLast();
            }

            // 队列尾部添加元素
            deque.addLast(i);

            // 当头部元素的idx超出窗口范围，那么需要移除头部元素
            if(deque.getFirst() <= i-k){
                deque.removeFirst();
            }

            // 保存结果，当i移动到最大位置时才保存结果
            if(i>=k-1){
                res[i-k+1] = nums[deque.getFirst()];
            }

        }
        return res;
    }

}
